package com.itheima;

import org.junit.Test;

import java.util.*;

public class StackProblem {

    public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList<>();
        int n = s.length();

        for(int i = 0; i < n; ++i) {
            char c = s.charAt(i);
            if(stack.isEmpty()) {
                stack.push(c);
            } else {
                char peek = stack.peek();
                if(c == ')') {
                    if(peek == '(') {
                        stack.pop();
                    } else {
                        stack.push(c);
                    }
                } else if(c == ']') {
                    if(peek == '[') {
                        stack.pop();
                    } else {
                        stack.push(c);
                    }
                } else if(c == '}') {
                    if(peek == '{') {
                        stack.pop();
                    } else {
                        stack.push(c);
                    }
                } else {
                    stack.push(c);
                }
            }
        }
        return stack.isEmpty();
    }

    public String topic394(String s) {

        Deque<Character> stack = new LinkedList<>();
        int n = s.length();
        int num = 0;
        for(int i = 0; i < n; ++i) {
            char c = s.charAt(i);
            if(c >= 'a' && c <= 'z' && num == 0) {
                stack.push(c);
            } else if(c >= '0' && c <= '9') {
                stack.push(c);
            } else if(c == '[') {
                num = 0;
                int j = 0;
                while(stack.peek() >= '0' && stack.peek() <= '9') {
                    int a = Integer.parseInt(String.valueOf(stack.peek()));
                    num = num + a * (int) Math.pow(10, j);
                    j++;
                }
            }
        }
        return s;
    }

    public String decodeString1(String s) {
        Deque<Character> stack = new LinkedList<>();
        int n = s.length();
        int num = 0;
        String res = "";
        for(int i = 0; i < n; ++i) {
            char c = s.charAt(i);
            if(c == '[') {
                //存储前i-j个的值并压栈
            }
        }
        int pre = 0;
        int i = 0;
        while(i < n) {
            char c = s.charAt(i);
            if(c == '[') {
                //存储pre - i 的值并开始压栈

                res = res + s.substring(pre, i);

                int j = i;
                for(j = i; j >= pre; j--) {
                    char c1 = s.charAt(j);
                    if(c1 >= 'a' && c1 <= 'z') {
                        break;
                    }
                }
                num = Integer.parseInt(s.substring(j + 1, i)); //转为int
                pre = i + 1;
                while(i < n) {
                    char c1 = s.charAt(i + 1);
                    if(c1 == ']') break;
                    else {
                        stack.push(c1);
                    }
                    i++;
                }
                String res1 = "";
                while(num >= 0) {
                    while(!stack.isEmpty()) {
                        char c1 = stack.pop();
                        res1 = c1 + res1;
                    }
                    num--;
                }
                res += res1;

            }
            i++;
        }
        return res;
    }

    public String decodeString(String s) {
        StringBuilder res = new StringBuilder(); //记录当前的string
        int inter = 0;
        Deque<String> res_stack = new LinkedList<>();
        Deque<Integer> inter_stack = new LinkedList<>();
        int n = s.length();

        for(char c : s.toCharArray()) {
            if(c == '[') {
                res_stack.push(res.toString());
                inter_stack.push(inter);
                inter = 0;
                res = new StringBuilder();

            } else if(c == ']') {
//                String t = res_stack.pop();
                StringBuilder sb = new StringBuilder(res);
                int num = inter_stack.pop();
                for(int i = 1; i < num; i++) {
                    sb.append(res);
                }
                String str = res_stack.pop() + sb.toString();
//                res_stack.push(str);
                res = new StringBuilder(str);
                num = 0;
            } else if(c >= '0' && c <= '9') {
                inter = inter * 10 + Integer.parseInt(c + "");
            } else {
                res.append(c);
            }
        }
        return res.toString();

    }

    public int[] dailyTemperatures_dp(int[] temperatures) {
        int n = temperatures.length;
        int[] dp = new int[n];

        dp[n - 1] = 0;
        for(int i = n - 2; i >= 0; i--) {
            dp[i] = Integer.MAX_VALUE;
        }
        for(int i = n - 2; i >= 0; i--) {
            for(int j = n - 1; j > i; j--) {
                if(temperatures[j] > temperatures[i]) {
                    dp[i] = Math.min(dp[i], j - i);
                }
            }
        }
        for(int i = n - 1; i >= 0; i--) {
            if(dp[i] == Integer.MAX_VALUE) {
                dp[i] = 0;
            }
        }
        return dp;
    }

    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for(int i = 1; i < n; i++) {
            if(temperatures[i] > temperatures[stack.peek()]) {
                while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                    int index = stack.pop();
                    ans[index] = i - index;
                }
                stack.push(i);
            } else {
                stack.push(i);
            }
        }
        while(!stack.isEmpty()) {
            int index = stack.pop();
            ans[index] = 0;
        }
        return ans;
    }

    public int largestRectangleArea(int[] heights) {
        int n = heights.length;

        Deque<Integer> stack = new LinkedList<>();
        int area = 0;
        stack.push(-1);
        stack.push(0);
        int i;
        for(i = 1; i < n; i++) {
            while(stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
                int height = heights[stack.pop()];
                int width = i - stack.peek() + 1;
                area = Math.max(area, width * height);
            }
            stack.push(i);
        }

        while(stack.peek() != -1) {
            int height = heights[stack.pop()];
            int width = i - stack.peek() + 1;
            area = Math.max(area, width * height);
        }

        return area;
    }

    @Test
    public void test() {

        System.out.println(dailyTemperatures(new int[]{73,74,75,71,69,72,76,73}));
    }

}

class MinStack {

    Deque<Integer> stack = new LinkedList<>();
    List<Integer> minList = new ArrayList<>(); //保存从小到大的数组
    int m = Integer.MAX_VALUE;

    public MinStack() {
        Deque<Integer> stack = new LinkedList<>();
        m = Integer.MAX_VALUE;
    }

    public void push(int val) {
        if(m == Integer.MAX_VALUE && m > val) {
            m = val;
        }
        else if(m > val) {
            m = val;
        }
        minList.add(val);
        stack.push(val);

    }

    public void pop() {
        if(stack.peek() == m) {
            minList.remove(Integer.valueOf(stack.pop()));
            Collections.sort(minList);
            m = minList.get(0);
        } else {
            minList.remove(Integer.valueOf(stack.peek()));

        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return m;
    }
}
